package sort;

/**
 * 二路归并排序
 *
 * @param <T>
 * @author zj
 */
public class MergeSort<T extends Comparable<T>> implements Sort<T> {

    @Override
    public void sort(T[] arr) {
        if (arr == null || arr.length == 0) {
            return;
        }
        mergeSort(arr, 0, arr.length - 1);
    }

    private void mergeSort(T[] arr, int low, int high) {
        if (low < high) { //大于的话是非法的，等于无需比较，小于才比较
            if ((high - low) == 1) { //只剩两个元素时，直接比较
                if (arr[low].compareTo(arr[high]) > 0) {
                    T tmp = arr[low];
                    arr[low] = arr[high];
                    arr[high] = tmp;
                }
            } else { //大于两个元素，继续递归
                int mid = (low + high) / 2;
                mergeSort(arr, low, mid); //递归排序前半段
                mergeSort(arr, mid + 1, high); //递归排序后半段
                merge(arr, low, mid, high); //将已排序的两段合并
            }
        }
    }

    /**
     * 合并数组相邻的已排序的两段，使得该段的元素整体有序
     *
     * @param arr
     * @param low
     * @param mid
     * @param high
     */
    private void merge(T[] arr, int low, int mid, int high) {
        int k = 0, i = low, j = mid + 1;
        Comparable tmp[] = new Comparable[high - low + 1];
        for (; i <= mid && j <= high; ) {
            if (arr[i].compareTo(arr[j]) <= 0) {
                tmp[k++] = arr[i++];
            } else {
                tmp[k++] = arr[j++];
            }
        }
        while (i <= mid) {
            tmp[k++] = arr[i++];
        }
        while (j <= high) {
            tmp[k++] = arr[j++];
        }
        for (i = low, k = 0; i <= high; i++, k++) {
            arr[i] = (T) tmp[k];
        }
    }
}
